package net.borderwars.map;

import net.borderwars.simulator.BattlePlane;
import net.borderwars.simulator.events.BEvent;
import net.borderwars.simulator.events.BoundryCrossing;
import net.borderwars.simulator.events.Collision;
import net.borderwars.simulator.events.DestinationReached;

import java.awt.*;
import java.io.Serializable;
import java.util.*;
import java.util.Map;
import java.util.logging.Logger;

/**
 * @author Eric
 *         Date: Mar 18, 2004
 *         Time: 10:21:35 AM
 */
public class QuadTree implements Serializable {

    private static final Logger log = Logger.getLogger ("net.borderwars.map.QuadTree");

    private static final int maxDepth = 10;
    private static final int maxPerCell = 5;
    private static final int minPerCell = 1; // this is the amount at which a cell would be collapsed

    private static int gid = 0;
    static private Canvas drawingSurface = null;

    // TODO: remove *ALL* drawing logic from QuadTree so that we can
    // TODO: multiple quadtree/maps running at time
    // TODO: as it is now.. just 1 map...  perhaps wrap root QuadTree in MAp object
    // TODO: and keep statics there?
    // TODO: or totally seperate the graphics... so some quadtrees don't even have hte logic
    // TODO: associated with them  instead they are run by...... events?
    // TODO: Or maybe Quadtree drawing is really only for debugging so its okay?
    // TODO: the real Client drawing will be seperate anyway?  hmm
    static int scaleXBy = 0;
    static int scaleYBy = 0;
    static int xShift = 0;
    static int yShift = 0;
    static boolean needsPaint = false;
    static BattlePlane bp = null;
    int id = gid++;

    private int totalSize = 0;
    private static final long serialVersionUID = -9010212101487432331L;

    public int getX1 () {
        return x1;
    }

    public int getX2 () {
        return x2;
    }

    public int getY1 () {
        return y1;
    }

    public int getY2 () {
        return y2;
    }

    private int x1,
            x2,
            y1,
            y2;
    private boolean isLeaf = true;
    private QuadTree children[] = null;
    private HashSet<Mappable> contained = new HashSet<Mappable> ();
    private QuadTree parent = null;
    private int depth = 0;
    private int width = 0;
    private int height = 0;
    private Line sides[] = null;
    private LinkedList<BEvent> colissionChecks = new LinkedList<BEvent> ();
    private static QuadTree root = null;

// --------------------------- CONSTRUCTORS ---------------------------

    public QuadTree (BattlePlane bpp, int width, int height) {
        this (bpp, -1 * width >> 1, height >> 1, width >> 1, -1 * height >> 1);
    }

    public QuadTree (BattlePlane bpp, int x1, int y1, int x2, int y2) {
        bp = bpp;
        this.x1 = x1;
        this.x2 = x2;
        this.y1 = y1;
        this.y2 = y2;
        width = Math.max (x2, x1) - Math.min (x2, x1);
        height = Math.max (y2, y1) - Math.min (y2, y1);
        if (root == null) {
            root = this;
        }
    }

    protected QuadTree (int x1, int y1, int x2, int y2, QuadTree parent) {
        this (bp, x1, y1, x2, y2);
        this.parent = parent;
        this.depth = parent.depth + 1;
    }

    public String toString () {
        return (id + ": (" + x1 + "," + y1 + ")" + "-(" + x2 + "," + y2 + ")" + "--(" + width + "," + height + ") " + isLeaf);
    }

    public Collection<Mappable> getMappables (int x, int y, int xx, int yy) {
        Collection<Mappable> rtn = new ArrayList<Mappable> ();
        getMappables (x, y, xx, yy, rtn);
        return (rtn);
    }

    /**
     * @param x
     * @param y
     * @param r
     * @param soFar
     */
    private void getMappables (int x, int y, int r, Collection<Mappable> soFar) {
        getMappables (new Location (x, y), r, soFar);
    }

    private void getMappables (Location l1, int r, Collection<Mappable> soFar) {
        if (isLeaf) {
            for (Mappable m : contained) {
                Location l2 = m.getLocation ();
                if (l1.distance (l2) <= r) {
                    soFar.add (m);
                }
            }
        }

        Rectangle rect = new Rectangle (10, 200, 40, 40);
        rect.intersects (rect);

    }

    private void getMappables (int x, int y, int xx, int yy, Collection<Mappable> soFar) {
        if (isLeaf) {
            for (Mappable m : contained) {
                Location l = m.getLocation ();
                if (x <= l.getX () && xx >= l.getX ()) {
                    if (y <= l.getY () && yy >= l.getY ()) {
                        soFar.add (m);
                    }
                }
            }
        }
        else {
            whichChild (x, y).getMappables (x, y, xx, yy, soFar);
            whichChild (x, yy).getMappables (x, y, xx, yy, soFar);
            whichChild (xx, yy).getMappables (x, y, xx, yy, soFar);
            whichChild (xx, y).getMappables (x, y, xx, yy, soFar);
        }

    }

    public int getTotalSize () {
        return totalSize;
    }

    public void add (Mappable m) {
        needsPaint = true;
        totalSize++;
        if (isLeaf) {
            if (contained.size () == maxPerCell && depth < maxDepth) { // time to expand our horizons
                expandThisNode ();
            }
            else {
                contained.add (m);
                return;
            }
        }
        QuadTree child = whichChild (m.getLocation ());
        child.add (m);
    }

    private QuadTree whichChild (Location l) {
        return (whichChild (l.getY (), l.getX ()));
    }

    private QuadTree whichChild (Mappable m) {
        Location l = m.getLocation ();
        return (whichChild (l.getY (), l.getX ()));
    }

    private void expandThisNode () {
        int sx = x1 + (width >> 1);
        int sy = y1 - (height >> 1);
        children = new QuadTree[4];

        children[0] = new QuadTree (x1, y1, sx, sy, this);
        children[1] = new QuadTree (sx + 1, y1, x2, sy, this);
        children[2] = new QuadTree (x1, sy + 1, sx, y2, this);
        children[3] = new QuadTree (sx + 1, sy + 1, x2, y2, this);
        isLeaf = false; // we are no longer a leaf
        // now iterate through our contents.. addthing them to the correct children
        removeObsoleteEvents ();

        for (Mappable aContained : contained) {
            totalSize--;
            this.add (aContained);
        }
        contained.clear ();
    }

    private QuadTree whichChild (int x, int y) {
        for (QuadTree lvChild : children) {
            if (lvChild.isInMe (x, y)) {
                return (lvChild);
            }
        }
        throw new UnsupportedOperationException (x + "," + y + " not found in " + x1 + "," + y1 + "," + x2 + "," + y2);
    }

    public int getHeight () {
        return (height);
    }

    public int getWidth () {
        return (width);
    }

    public void mapPaint (Canvas c) {
        setCanvas (c);

        if (!needsPaint) {
            return;
        }

        int xsize = c.getWidth ();
        int ysize = c.getHeight ();
        xShift = xsize >> 1;
        yShift = ysize >> 1;
        scaleXBy = width / xsize;
        scaleYBy = height / ysize;
        //  System.err.println("Scaling values " + scaleXBy + "," + scaleYBy+ " " + xShift +"," + yShift);

        Image offScreen = c.createImage (xsize, ysize);

        Graphics offScreenG = offScreen.getGraphics ();
        offScreenG.setColor (Color.BLACK);
        offScreenG.fillRect (0, 0, xsize, ysize);

        //  mapPaint(offScreenG, true);
        c.getGraphics ().drawImage (offScreen, 0, 0, xsize, ysize, null);
        needsPaint = false;
    }

    static public void setCanvas (Canvas drawingCanvas) {
        drawingSurface = drawingCanvas;
    }

    /* private void mapPaint(Graphics g, boolean recurse) {
         if (recurse) {

         }
         g.setColor(Color.BLUE);


         int s1 = (x1 / scaleXBy) + xShift;
         int s2 = yShift - (y1 / scaleYBy);

         int swidth = width / scaleXBy;
         int sheight = height / scaleYBy;


         Rectangle r = new Rectangle(s1, s2, swidth, sheight);
         //System.err.println("DrawR " + r + "  " + this);
         g.drawRect(r.x, r.y, r.width, r.height);
         if (isLeaf) {
             g.setColor(Color.RED);
             for (Iterator i = contained.iterator(); i.hasNext();) {
                 Mappable m = (Mappable) i.next();
                 g.drawRect(m.getLocation().getX() / scaleXBy + xShift, yShift - m.getLocation().getY() / scaleYBy, m.getWidth() / scaleXBy, m.getHeight() / scaleYBy);
             }
         } else {
             for (int i = 0; i < children.length; i++) {
                 QuadTree lvChild = children[i];
                 lvChild.mapPaint(g, true);
             }
         }
     }*/

    public void remove (Mappable m) {
        needsPaint = true;
        totalSize--;
        // todo: Removed this to make sure it wasn't causing a problem

//        if (!isLeaf && totalSize <= minPerCell && parent != null) {
//            // if this node can no longer justify
//            // and we aren't the root node
//            // and we aren't a leaf
//            collapseThisNode();
//            contained.remove(m);
//        }
//        else
        if (isLeaf) {
            boolean b = contained.remove (m);

            if (!b) {
                log.severe ("element not found in node!");
                log.severe ("root " + root + " " + root.contained);
                log.severe ("this " + this + " " + this.contained);
                log.severe ("looking for " + m.getLocation () + " " + isInMe (m.getLocation ()));
                Thread.dumpStack ();
                System.exit (1);
            }
        }
        else {
            QuadTree child = whichChild (m);
            child.remove (m);
        }
    }

    private void collapseThisNode () {
        isLeaf = true; // mark ourselves as a leaf
        ArrayList<Mappable> reAdd = new ArrayList<Mappable> (maxPerCell << 2);
        for (QuadTree lvChild : children) {
            reAdd.addAll (lvChild.contained);
        }
        children = null;
        removeObsoleteEvents ();
        for (Mappable m : reAdd) {
            this.add (m);
        }

    }

    private void removeObsoleteEvents () {
        for (BEvent cc : colissionChecks) {
            bp.getEventQueue ().remove (cc);
        }
    }

    public BEvent add (Movable m) {

        needsPaint = true;
        totalSize++;
        if (isLeaf) {  // if I will store this sucker
            if (contained.size () == maxPerCell && depth < maxDepth) { // time to expand our horizons
                expandThisNode ();
            }
            else {
                if (!isInMe (m.getLocation ().getX (), m.getLocation ().getY ())) {
                    Thread.dumpStack ();
                    throw new UnsupportedOperationException ("Something broke and we are adding to the wrong region\n" + m + "\n" + this);

                }
                contained.add (m);
                Location destination = m.getDestination ();
                if (isInMe (destination)) { // if the final destination is within me
                    long t = whenDoesMappableReach (m, destination);
                    t += bp.getClock ().getCurrentTime ();
                    DestinationReached dr = new DestinationReached (t, destination, m);
                    colissionChecks.add (dr);
                    return (dr);
                }

                Collision c = collisionCheck ();
                if (c != null) {
                    // keep a note of it so we can make sure to pass it on during expansion/collapsion
                    colissionChecks.add (c);
                    return (c);
                }
                Location exitPoint = whereDoesMappableLeave (m);
                long when = whenDoesMappableReach (m, exitPoint);
                // when = fudge(m, p, when);

                if (when == 0) {
                    log.severe (m + " crosses NOW? @ " + exitPoint + " and we are " + this);
                    return (null);
                }
                else {
                    when += bp.getClock ().getCurrentTime ();
                    BoundryCrossing cb = new BoundryCrossing (when, m, root, exitPoint);
                    colissionChecks.add (cb);
                    return (cb);
                }
            }
        }
        QuadTree child = whichChild (m.getLocation ().getX (), m.getLocation ().getY ());

        return (child.add (m));
    }

    private Collision collisionCheck () {
        //System.err.println("Collision Check");
        return (null);
    }

    private Location whereDoesMappableLeave (Movable m) {
        if (sides == null) {
            calculateSides ();
        }
        Location exitPoint = whichPointDoesItLeaveAt (m);
        if (drawingSurface != null) {
            drawingSurface.getGraphics ().setColor (Color.GREEN);
            try {
                drawingSurface.getGraphics ().drawRect (exitPoint.getX (), exitPoint.getY (), 3, 3);
            }
            catch (Exception e) {
                log.severe ("@" + bp.getClock ().getCurrentTime () + " " + m);
                e.printStackTrace ();
            }
        }
        return (exitPoint);
    }

    private void calculateSides () {
        sides = new Line[4];
        sides[0] = new Line (x1, y1, x2, y1); //top
        sides[1] = new Line (x2, y1, x2, y2); // right
        sides[2] = new Line (x2, y2, x1, y2); //bottom
        sides[3] = new Line (x1, y2, x1, y1); //left
    }

    public static StringBuffer errorString = null;

    private Location whichPointDoesItLeaveAt (Movable m) {
        Line ml = calcDirectionLine (m);

        errorString = new StringBuffer ();

        errorString.append (m.toString () + "\n");

        TreeMap<Long, Location> sortedPoints = new TreeMap<Long, Location> ();
        for (Line lvSide : sides) {
            errorString.append ("\tCheck intersection side: " + lvSide + " ");
            Location intersectPoint = ml.intersects (lvSide); // find where they intersect
            if (intersectPoint == null) {
                log.severe ("Make sure these guys don't intersect ");
                log.severe ("one " + ml);
                log.severe (" two " + lvSide);

            }
            else {  // if no intersect.. then it doesn't hit that side!

                long t = whenDoesMappableReach (m, intersectPoint);
                errorString.append ("\t\tInserting into sortlist " + intersectPoint + " with a key of " + t + "\n");
                sortedPoints.put (t, intersectPoint);
            }
        }
        //  note... don't think we can just grab the 2nd, or 3rd one
        // because sometimes you will get duplicates if your direction
        // is equadistant between two points in the past

        Iterator i = sortedPoints.entrySet ().iterator ();
        errorString.append ("\t\tsortedPoints.size() " + sortedPoints.size ());
        int futureStamp = Integer.MIN_VALUE;
        Map.Entry e = null;
        while (futureStamp <= 0) {              // skip past the ones in the past
            e = (Map.Entry) i.next ();
            futureStamp = ((Integer) e.getKey ());
        }
        // now we are at the first positive one
        assert (e != null);
        Location ip = (Location) e.getValue ();

        if (ip == null) {
            log.severe ("What no intersections?  ");
            log.severe ("This region " + this);
            log.severe (errorString.toString ());
            System.exit (1);
        }
        return (ip);
    }

    private Line calcDirectionLine (Movable m) {
        Location current = m.getLocation ();
        Location dest = m.getDestination ();
        Line rtn = new Line (current.getX (), current.getY (), dest.getX (), dest.getY ());
        return (rtn);
    }

    private boolean isInMe (Location l) {
        return (isInMe (l.getX (), l.getY ()));
    }

    private boolean isInMe (int x, int y) {
        if (x >= x1 && x <= x2) {
            if (y <= y1 && y >= y2) {
                return true;
            }
        }
        return (false);
    }

//    private boolean isInFrontOfRobot(net.borderwars.map.Point p, Movable m) {
//        // first calc our x velocity vector
//        if (m.getVelocity().getDirection() == 0) {
//            throw new UnsupportedOperationException("another 0 direction!!!! " + m);
//        }
//        if (m.getVelocity().getVX() == 0) {
//            throw new UnsupportedOperationException("No X Velocity? " + m);
//        }
//
//        long scale = 2 ^ 48;
//        Location current = m.getLocation();
//        Location future = current.project(scale, m.getVelocity());
//
//        Rectangle r = new Line(current.getX(), current.getY(), future.getX(), future.getY()).getBounds();
//        if (r.contains(p)) {
//            log.severe(" within " + r);
//            return (true);
//        }
//        else {
//            log.severe(" outside " + r);
//            return (false);
//        }
//
//        net.borderwars.map.Point mp = new net.borderwars.map.Point(m.getLocation().getX(), m.getLocation().getY());
//
//        double aa = angleFrom(mp, p); // angle between our current location and the proposed location
//        //double vaa = angleFrom(mp, new Point(mp.x + m.getVx(), mp.y + m.getVy() )); // angle from current location and our velocity vector
//
//        double v = aa - m.getDirection();
//        if (v < (Math.PI / 2)) { // if its an acute angle
//            return (true);
//        }
//        log.severe("The angle delta was " + v + " " + Math.PI / 2 + " " + p);
//        return (false);

//        // how long until we reach p.x
//        double t = (p.x - m.getLocation().getX()) / m.getVx();
//        // if its int he past.. then the point is behind us!
//        boolean rtn = false;
//        if (t < 0) {
//
//            rtn  = false;
//        } else {
//            rtn = true;
//        }
//           if (m instanceof Robot) {
//                Robot o = (Robot) m;
//                log.severe(o.toString() + " p.x, m.getLocation().getX() / getVx" + " " + p +"-"+m.getLocation().getX() +"/" + m.getVx() + "="+t + " "  + rtn);
//            } else {
//                log.severe(m.toString() + " p.x, m.getLocation().getX() / getVx" + " " + p  +"-"+m.getLocation().getX() +"/" + m.getVx() + "="+t+ " " + rtn);
//            }
//        return(rtn);
    //  }

//    private double angleFrom(net.borderwars.map.Point a, net.borderwars.map.Point b) {
//        double dx = b.x - a.x;
//        double dy = b.y - a.y;
//        double angle = Math.atan2(dx, dy);
//        return (angle);
//    }

    private long whenDoesMappableReach (Movable m, Location p) {
        int distance = m.getLocation ().distance (p);
        long time = distance / m.getVelocity ().getSpeed ();
        if (time < 1) {
            log.severe ("We don't ahve enough percision on our clock to say how long this will take");
            System.exit (1);
        }
        return (time);
    }

    public QuadTree[] getChildren () {
        return (children);
    }

    public boolean isLeaf () {
        return (isLeaf);
    }

    public Collection<Mappable> getMappables () {
        ArrayList<Mappable> items = new ArrayList<Mappable> (totalSize);
        getMappables (items);
        return (items);
    }

    private void getMappables (ArrayList<Mappable> items) {
        if (isLeaf) {
            items.addAll (contained);
        }
        else {
            for (QuadTree child : children) {
                child.getMappables (items);
            }
        }

    }
}
